package org.example.myleet.p915;

import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;

public class Solution {
    public int partitionDisjoint(int[] nums) {
        Map<Integer, Integer> numCount = new HashMap<>();
        for (int num : nums) {
            numCount.put(num, numCount.getOrDefault(num, 0) + 1);
        }
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        for (int num : nums) {
            pq.offer(num);
        }
        int maxLeft = nums[0];
        for (int i = 0; i < nums.length - 1; ++i) {
            numCount.put(nums[i], numCount.getOrDefault(nums[i], 0) - 1);
            maxLeft = Math.max(maxLeft, nums[i]);
            while (numCount.getOrDefault(pq.peek(), 0) == 0) {
                maxLeft = Math.max(maxLeft, pq.poll());
            }
            if (maxLeft <= pq.peek()) {
                return i + 1;
            }
        }
        return 1;
    }
}
